package com.fanshuai.algorithms.backtrack;

import com.fanshuai.algorithms.datastructure.graph.DirectGraph;

import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;

import static java.util.Collections.reverse;

/**
 * 单源最短路径算法  回溯法实现
 *
 * dist[i] 表示最短路径数组。
 * 从src节点开始，以深度优先的方式遍历图，不断更新最短路径数组
 * 分支限界函数： matrix[cur][i] < inf && dist[cur] + matrix[cur][i] < dist[i]
 */
public class MinPath {
    /**
     * @param matrix  邻接矩阵
     * @return  最短路径
     */
    public static int minPath(int[][] matrix, int src, int desc, List<Integer> path) {
        int n = matrix.length;
        int[] dist = new int[n];
        int[] parent = new int[n];
        dist[src] = 0;
        parent[src] = src;
        for (int i = 0; i < n && i != src; i++) {
            dist[i] = Integer.MAX_VALUE;
            parent[i] = -1;
        }

        //深度优先遍历
        minPath0(matrix, src, dist, parent);

        int i = desc;
        while (parent[i] != i && parent[i] != -1) { //通过指向父节点的树，计算最短路径
            path.add(i);
            i = parent[i];
        }
        if (parent[i] != -1) {
            path.add(i);
        }
        reverse(path);
        return dist[desc];
    }

    private static void minPath0(int[][] matrix, int cur, int[] dist, int[] parent) {
        //限界函数  matrix[cur][i] < inf && dist[cur] + matrix[cur][i] < dist[i]
        for (int i = 0; i < matrix.length && i != cur; i++) {
            if (matrix[cur][i] < Integer.MAX_VALUE && dist[cur] + matrix[cur][i] < dist[i]) {
                //更新dist数组
                dist[i] = dist[cur] + matrix[cur][i];
                parent[i] = cur;
                minPath0(matrix, i, dist, parent);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        DirectGraph<Integer> graph = new DirectGraph<>(6);

        String path = System.getProperty("user.dir") + "/src/main/java/com/fanshuai/algorithms/branch/";
        List<String> lines = Files.readAllLines(Paths.get(path + "graph1"));

        for (int i = 2; i < lines.size(); i++) {
            String line = lines.get(i);
            String[] arr = line.split(" ");

            int x = Integer.valueOf(arr[0]);
            int y = Integer.valueOf(arr[1]);
            int weight = Integer.valueOf(arr[2]);
            graph.addEdge(x, y, weight);
        }

        int[][] pairs = new int[][] {{1, 2}, {1, 3}, {1, 4}, {1, 5},
                {1, 6}, {3, 4}, {3, 6}, {4, 6}};

        for (int[] pair: pairs) {
            List<Integer> list = new ArrayList<>();
            int min = minPath(graph.getMatrix(), pair[0], pair[1], list);
            System.out.println(String.format("min path=%d, path=%s", min, list));
        }
    }
}
